This invention relates to a turbo decoding method and apparatus. More particularly, the invention relates to a turbo decoding method and apparatus for performing turbo decoding at high speed without reducing number of iterations and without causing a decline in encoding gain.
Error correction codes are for the purpose of correcting error contained in received information or in reconstructed information, etc., so that the original information can be decoded correctly. These are applied to a variety of systems. For example, error correction codes are applied in cases where data is to be transmitted without error when performing mobile communication, facsimile or other data communication, or in cases where data is to be reconstructed without error from a large-capacity storage medium such as a magnetic disk or CD.
Among the available error correction codes, turbo code (see the specification of U.S. Pat. No. 5,446,747) recently has become the focus of attention as code having a high encoding gain. Studies for putting such code into use are proceeding and implementation of such code in third-generation mobile telephone systems has been decided. In such turbo code, MAP (Maximum A Posteriori Probability) decoding and the SOVA (Soft Output Viterbi Algorithm) bring forth major effects. A case where MAP decoding is employed will now be described.
Communication System Including a Turbo Encoder and a Turbo Decoder
FIG. 26 if a block diagram of a communication system that includes a turbo encoder and a turbo decoder. Specifically, the system includes a turbo encoder 101 provided on the data transmitting side, a turbo decoder 102 provided on the data receiving side, and a data communication path 103. Further, character u represents transmit information data of length N; xa, xb, xc represent encoded data obtained by encoding the information data u by the turbo encoder 101; ya, yb, yc denote receive signals that have been influenced by noise and fading as a result of propagation of the encoded data xa, xb, xc through the communication path 13; and u′ represents results of decoding obtained by decoding the receive data ya, yb, yc by the turbo decoder 12. These items of data are as expressed below.
                              Original          ⁢                                          ⁢                      data            :                                                  ⁢            u                          =                  {                                    u              ⁢                                                          ⁢              1                        ,                          u              ⁢                                                          ⁢              2                        ,                          u              ⁢                                                          ⁢              3                        ,                                                  ⁢            …            ⁢                                                  ,                          u              N                                }                                                  Encoded          ⁢                                          ⁢                      data            :                                                  ⁢            xa                          =                  {                                    x                              a                ⁢                                                                  ⁢                1                                      ,                          x                              a                ⁢                                                                  ⁢                2                                      ,                          x                              a                ⁢                                                                  ⁢                3                                      ,                                                  ⁢            …            ⁢                                                  ,                          x                              a                ⁢                                                                  ⁢                k                                      ,                                                  ⁢            …            ⁢                                                  ,                          x                              a                ⁢                                                                  ⁢                N                                              }                                                  :                                          ⁢          xb                =                  {                                    x                              b                ⁢                                                                  ⁢                1                                      ,                          x                              b                ⁢                                                                  ⁢                2                                      ,                          x                              b                ⁢                                                                  ⁢                3                                      ,                                                  ⁢            …            ⁢                                                  ,                          x                              b                ⁢                                                                  ⁢                k                                      ,                                                  ⁢            …            ⁢                                                  ,                          x                              b                ⁢                                                                  ⁢                N                                              }                                                  :                                          ⁢          xc                =                  {                                    x                              c                ⁢                                                                  ⁢                1                                      ,                          x                              c                ⁢                                                                  ⁢                2                                      ,                          x                              c                ⁢                                                                  ⁢                3                                      ,                                                  ⁢            …            ⁢                                                  ,                          x                              c                ⁢                                                                  ⁢                k                                      ,                                                  ⁢            …            ⁢                                                  ,                          x                              c                ⁢                                                                  ⁢                N                                              }                                                  Receive          ⁢                                          ⁢                      data            :                                                  ⁢            ya                          =                  {                                    y                              a                ⁢                                                                  ⁢                1                                      ,                          y                              a                ⁢                                                                  ⁢                2                                      ,                          y                              a                ⁢                                                                  ⁢                3                                      ,                                                  ⁢            …            ⁢                                                  ,                          y                              a                ⁢                                                                  ⁢                k                                      ,                                                  ⁢            …            ⁢                                                  ,                          y                              a                ⁢                                                                  ⁢                N                                              }                                                  :                                          ⁢          yb                =                  {                                    y                              b                ⁢                                                                  ⁢                1                                      ,                          y              b2                        ,                          y                              b                ⁢                                                                  ⁢                3                                      ,                                                  ⁢            …            ⁢                                                  ,                          y                              b                ⁢                                                                  ⁢                k                                      ,                                                  ⁢            …            ⁢                                                  ,                          y                              b                ⁢                                                                  ⁢                N                                              }                                                  :                                          ⁢          yc                =                  {                                    y                              c                ⁢                                                                  ⁢                1                                      ,                          y                              c                ⁢                                                                  ⁢                2                                      ,                          y                              c                ⁢                                                                  ⁢                3                                      ,                                                  ⁢            …            ⁢                                                  ,                          y                              c                ⁢                                                                  ⁢                k                                      ,                                                  ⁢            …            ⁢                                                  ,                          y                              c                ⁢                                                                  ⁢                N                                              }                    
The turbo encoder 101 encodes the information data u of information length N and outputs the encoded data xa, xb, xc. The encoded data xa is the information data upper se, the encoded data xb is data obtained by the convolutional encoding of the information data u by an encoder ENC1, and the encoded data xc is data obtained by the interleaving (.) and convolutional encoding of the information data u by an encoder ENC2. In other words, a turbo code is obtained by combining two convolutional codes. It should be noted that an interleaved output xa′ differs from the encoded data xa only in terms of its sequence and therefore is not output.
Turbo Encoder
FIG. 27 is a diagram showing the details of the turbo encoder 101. Encoders ENC1, ENC2 are identically constructed convolutional encoders and are connected to an interleaving unit (interleaver). The convolutional encoders ENC1, ENC2, which are adapted to output recursive systematic convolutional codes, are each constructed by connecting three flip-flops FF1, FF2, FF3, four exclusive-OR gates EXOR1 to EXOR4 and a switch SW in the manner illustrated. The switch SW is for adding on a tail bit and usually inputs data u, u″ to an exclusive-OR gate EOR1. However, upon completion of input of data information consisting of N bits, which is one encoding unit, the switch SW is switched to the state illustrated, the flip-flops FF1, FF2, FF3 are made all “0”s by three clock pulses and 3-bit tail bits are added to the tail ends of the transmitted codes xa, xb, xc.
The flip-flops FF1, FF2, FF3 each take on a total of eight states 0 to 7, namely (000), (001), (010), (011), (100), (101), (110) and (111). If 0 or 1 is input to the flip-flops in each of these states, the states of the flip-flops undergo a transition as illustrated in FIG. 28 and the flip-flops output xa, xb. In FIG. 28, the left side indicates the state prior to input of receive data, the right side the state after the input, the solid lines the path of the state transition when “0” is input and the dashed lines the path of the state transition when “1” is input, and 00, 11, 10, 01 on the paths indicate the values of the output signals xa, xb. By way of example, if “0” is input in the state 0: (000), the outputs xa, xb will be 00 and the state becomes 0: (000); if “1” is input, the outputs xa, xb will be 11 and the state becomes 4: (100).
Turbo Decoder
FIG. 29 is a block diagram of the turbo decoder. Turbo decoding is performed by a first element decoder DEC1 using ya and yb first among the receive signals ya, yb, yc. The element decoder DEC1 is a soft-output element decoder and outputs the likelihood of decoded results. Next, similar decoding is performed by a second element decoder DEC2 using the likelihood, which is output from the first element decoder DEC1, and yc. That is, the second element decoder DEC2 also is a soft-output element decoder and outputs the likelihood of decoded results. Here yc is a receive signal corresponding to xc, which was obtained by interleaving and encoding the information data u. Accordingly, the likelihood that is output from the first element decoder DEC1 is interleaved by an interleaver (.) before it enters the second element decoder DEC2.
The likelihood output from the second element decoder DEC2 is deinterleaved by a deinterleaver (.−1) and then is fed back as the input to the first element decoder DEC1. Further, u′ is decoded data (results of decoding) obtained by rendering a “0”, “1” decision regarding the interleaved results from the second element decoder DEC2. Error rate is reduced by repeating the above-described decoding operation a prescribed number of times.
MAP decoders can be used as the first and second element decoders DEC1 and DEC2 in such a turbo element decoder.
Basic MAP Decoding Method According to the Prior Art
FIG. 30 is a diagram showing the structure of a MAP decoder for implementing a basic MAP decoding method according to the prior art. Encoding rate R, information length N, original information u, encoded data xa, xb and receive data ya, yb are as follows:                encoding rate: R=½        information length: N        
                              original          ⁢                                          ⁢                      information            :                                                  ⁢            u                          =                  u          ⁢                      {                                          u                1                            ,                              u                2                            ,                              u                3                            ,                                                          ⁢              …              ⁢                                                          ,                              u                N                                      }                                                            encoded          ⁢                                          ⁢                      data            :                                                  ⁢                          x              a                                      =                  {                                    x                              a                ⁢                                                                  ⁢                1                                      ,                          x                              a                ⁢                                                                  ⁢                2                                      ,                          x                              a                ⁢                                                                  ⁢                3                                      ,                                                  ⁢            …            ⁢                                                  ,                          x                              a                ⁢                                                                  ⁢                k                                      ,                                                  ⁢            …            ⁢                                                  ,                          x                              a                ⁢                                                                  ⁢                N                                              }                                                  :                                          ⁢                      x            b                          =                  {                                    x                              b                ⁢                                                                  ⁢                1                                      ,                          x                              b                ⁢                                                                  ⁢                2                                      ,                          x                              b                ⁢                                                                  ⁢                3                                      ,                                                  ⁢            …            ⁢                                                  ,                          x                              b                ⁢                                                                  ⁢                k                                      ,                                                  ⁢            …            ⁢                                                  ,                          x                              b                ⁢                                                                  ⁢                N                                              }                                                  receive          ⁢                                          ⁢                      data            :                                                  ⁢                          y              a                                      =                  {                                    y                              a                ⁢                                                                  ⁢                1                                      ,                          y                              a                ⁢                                                                  ⁢                2                                      ,                          y                              a                ⁢                                                                  ⁢                3                                      ,                                                  ⁢            …            ⁢                                                  ,                          y                              a                ⁢                                                                  ⁢                k                                      ,                                                  ⁢            …            ⁢                                                  ,                          y                              a                ⁢                                                                  ⁢                N                                              }                                                  :                                          ⁢                      y            b                          =                  {                                    y                              b                ⁢                                                                  ⁢                1                                      ,                          y              b2                        ,                          y                              b                ⁢                                                                  ⁢                3                                      ,                                                  ⁢            …            ⁢                                                  ,                          y                              b                ⁢                                                                  ⁢                k                                      ,                                                  ⁢            …            ⁢                                                  ,                          y                              b                ⁢                                                                  ⁢                N                                              }                    More specifically, encoded data xa, xb is generated from original information u of information length N. At the time of reception, error is inserted into the encoded data and the data ya, yb is received, and it is assumed that the original information u is decoded from the received data. Though length actually is greater than N bits the encoded data xa, xb includes tail bits, the description will be rendered based upon a length of N bits.
If a shift-probability calculation unit 1 receives (yak,ybk) at time k, the unit 1 calculates:
probability γ0,k that (xak,xbk) is (0,0);
probability γ1,k that (xak,xbk) is (0,1);
probability γ2,k that (xak,xbk) is (1,0); and
probability γ3,k that (xak,xbk) is (1,1);
and stores these probabilities in a memory 2.
Using forward probability α1,k−1(m) that original data uk−1 is “1”, forward probability α0,k−1(m) that the original data uk−1 is “0” and the obtained shift probabilities γ0,k, γ1,k, γ2,k, γ3,k at time k, a forward-probability calculation 3 calculates forward probability α1,k(m) that original data uk is “1” and forward probability α0,k(m) that original data uk is “0” at time k in each state m (=0 to 7) at an immediately preceding time (k−1), and stores these probabilities in memories 4a to 4h. It should be noted that since processing always starts from state m=0, the initial values of forward probabilities are α0,0(0)=α1,0(0)=1, α0,0(m)=α1,0(m)=0 (where m 0).
The shift-probability calculation unit 1 and forward-probability calculation unit 3 repeat the above-described calculations at k=k+1, perform the calculations from k=1 to k=N to calculate the shift probabilities γ0,k, γ1,k, γ2,k, γ3,k and forward probabilities α1,k(m), α0,k(m) at each of the times k=1 to N and store these probabilities in memory 2 and memories 4a to 4h, respectively.
Thereafter, a backward-probability calculation unit 5 calculates the backward probability βk(m) (m=0 to 7) in each state m (=0 to 7) at time k using the backward probability βk+1(m) and shift probability γs,k+1 (m=0 to 7) at time (k+1), where it is assumed that the initial value of k is N−1, that the trellis end state is m=0 and that βN(0)=1, βN(m)=0 (m 0) hold.
A first arithmetic unit 6a in a joint-probability calculation unit 6 multiplies the forward probability α1,k(m) and backward probability βk(m) in each state m (=0 to 7) at time k to calculate the probability λ1,k(m) that the kth item of original data uk is “1”, and a second arithmetic unit 6b in the joint-probability calculation unit 6 multiplies the forward probability α0,k(m) and backward probability βk(m) in each state m (=0 to 7) at time k to calculate the probability λ0,k(m) that the kth item of original data uk is “0”.
An a posteriori probability calculation unit 7 adds the “1” probabilities λ1,k(m) (m=0 to 7) in each of the states m (=0 to 7) at time k and adds the “0” probabilities λ0,k(m) (m=0 to 7) in each of the states m (=0 to 7) to obtain the probability summations ˜mλ1,k(m) and ˜mλ0,k(m), and outputs a logarithmic likelihood [a posteriori probability L(u1k)] in accordance with the following equation:L(u1k)=log [˜mλ1,k(m)/˜mλ0,k(m)]  (1)Since a posteriori probability L(u1k) includes a priori likelihood and a communication-path value that prevail at time of input, an external-information likelihood calculation unit 8 deletes this portion, calculates external-information likelihood Le(u1k), stores this value and outputs this as a priori likelihood L(u1k′) in ensuing decoding processing.
The backward-probability calculation unit 5, joint-probability calculation unit 6 and a posteriori probability calculation unit 7 subsequently repeat the foregoing calculations at k=k−1, perform the calculations from k=N to k=1 to calculate the a posteriori probability L(u1k), and output the same.
Thus, the first cycle of the first half of decoding processing of turbo code ends, then a signal that is the result of interleaving the receive signal ya and the a priori likelihood L(u1k) that was obtained in the first half of decoding processing are regarded as being a new receive signal ya′, the above-described decoding processing is executed using ya′ and yc, and likelihood L(u2k) obtained is output. If a posteriori likelihood L(u8k)>0 holds when decoding processing has subsequently been repeated a number of times, e.g., eight times, the decoded result uk=1 is output; if L(u8k)<0 holds, then the decoded result uk=0 is output.
With the basic MAP decoding method set forth above, memory of 4×N is required for storing shift probability and memory of m (the number of states)×2×N is required for storing forward probability, meaning that a total memory of (4+m×2)×N is required. Since actual calculation is accompanied by soft-decision signals, a large amount of additional memory which is eight times this figure is required.
First MAP Decoding Method According to the Prior Art
In order to cut down on memory, therefore, a method of performing calculation upon interchanging the order in which forward probability and backward probability are calculated has been considered. FIG. 31 is a block diagram of a turbo decoder that adopts this first MAP decoding method according to the prior art. Here components identical with those shown in FIG. 30 are designated by like reference characters. In the turbo decoder of FIG. 31, one MAP unit is used alternately as the first and second element decoders DEC1, DEC2 in FIG. 29, and an interleave RAM 11 is used alternately as the interleaver (.) and deinterleaver (.−1) in FIG. 29.
A RAM 9 for communication-path values stores the receive data ya, yb, yc and outputs data upon appropriately interchanging the outputs in terms of the order thereof. The RAM 9 has a memory for storing all receive data and a data output unit for outputting the receive data in an order that is different from or the same as the input order.
Using receive data (yak,ybk) at time k (=N), the shift-probability calculation unit 1 calculates the following probabilities:
probability γ0,k that (xak,xbk) is (0,0);
probability γ1,k that (xak,xbk) is (0,1);
probability γ2,k that (xak,xbk) is (1,0); and
probability γ3,k that (xak,xbk) is (1,1).
Using backward probability βk(m) and shift probability γs,k (s=0 to 3) at time k (=N), the backward-probability calculation unit 5 calculates the backward probability βk−1(m) (m=0 to 7) in each state m (=0 to 7) at time k−1 and stores this in a backward probability RAM 10. The shift-probability calculation unit 1 and backward-probability calculation unit 5 then repeat the above operations at k=k−1, perform the operations from k=N to k=1 to calculate the backward probability βk (m) at each of the times k=1 to N and store these backward probabilities in the backward-probability RAM 10.
Thereafter, using forward probability α1,k−1(m) that original data uk−1 is “1”, forward probability α0,k−1(m) that the original data uk−1 is “0” and the shift probabilities γ0,k, γ1,k, γ2,k, γ3,k at time k−1, the forward-probability calculation 3 calculates forward probability α1,k(m) that uk is “1” and forward probability α0,k(m) that uk is “0” in each state m (=0 to 7) at time k, where the initial value of k is 1. The joint-probability calculation unit 6 multiplies the forward probability α1,k(m) in each of the states 0 to 7 at time k and backward probability βk(m), which has been stored in the RAM 10, to calculate the probability λ1,k(m) that the kth item of original data uk is “1”. Similarly, the joint-probability calculation unit 6 multiplies the forward probability α0,k(m) in each of the states 0 to 7 at time k and backward probability βk(m) to calculate the probability λ0,k(m) that the original data uk is “0”.
The a posteriori probability calculation unit 7 adds the “1” probabilities λ1,k(m) (m=0 to 7) in each of the states m (=0 to 7) at time k and adds the “0” probabilities λ0,k(m) (m=0 to 7) in each of the states m (=0 to 7) to obtain the “1” probability summation ˜mλ1,k(m) and “0” probability summation ˜mλ0,k(m), and outputs the logarithmic likelihood [a posteriori probability L(u1k)] in accordance with Equation (1). Since a posteriori probability L(u1k) includes a priori likelihood and a communication-path value that prevail at time of input, the external-information likelihood calculation unit 8 deletes this portion and calculates external-information likelihood Le(u1k). This is interleaved by the interleave RAM 11, which outputs the result as a priori likelihood L(u1k′) in ensuing decoding processing.
Thus, the first cycle of the first half of decoding processing of turbo code ends, then a signal that is the result of interleaving the receive signal ya and the a priori likelihood L(u1k) that was obtained in the first half of decoding processing are regarded as being a new receive signal ya′, the above-described decoding processing is executed using ya′ and yc, and likelihood L(u2k) obtained is output. Thereafter, when decoding processing has been repeated a number of times, e.g., eight times, decoded result uk=1 is output if a posteriori probability L (u8k)>0 holds and decoded result uk=0 is output if a posteriori probability L (u8k)<0 holds.
FIG. 32 is a diagram useful in describing operation according to first MAP decoding method of the prior art, and FIG. 33 is a MAP time chart. According to the first MAP decoding method, calculation of shift probability, calculation of backward probability and processing for storing backward probability β in memory are performed in the first half of decoding, and calculation of shift probability, calculation of forward probability, calculation of joint probability, and calculation of a posteriori probability and external information likelihood are performed in the second half of decoding. More specifically, according to the first MAP decoding method, backward probability βk(m) is stored without storing shift probability and forward probability α1,k(m). As a result, memory required with the first MAP decoding method is only that required for storing the backward probability, namely m (number of states)×N. The necessary memory is a total of (4+m)×N, which means that the amount of memory can be reduced over that required for the basic MAP decoding method.
FIG. 34 is a block diagram illustrating the details of the RAM 9, which stores communication-path values, and of the interleave RAM 11 in the turbo decoder of FIG. 31. Components identical with those of the turbo decoder in FIG. 31 are designated by like reference characters.
A MAP controller 21 controls the various timings of the MAP decoder in accordance with the operation sequence shown in FIG. 33. The RAM 9 has RAMs 9a to 9c and a RAM controller 9d for controlling the reading and writing of receive data. The RAMs 9a to 9c store the receive data ya, yb, yc, respectively, which is soft-decision data obtained by quantization at n bits each, and the RAM controller 9d appropriately outputs receive data in the order in which the data was input and changes the output sequence to thereby perform interleaving of the receive data. A backward-probability RAM 10 has a β-storing RAM 10a and a controller 10b of a backward-probability RAM. In a first cycle of MAP decoding, the external-information likelihood calculation unit 8 outputs the external-information likelihood Le(u) using the a posteriori probability L(u) output from the a posteriori probability calculation unit 7 and the MAP-decoder input signal (=signal ya). A write controller 11a writes the external-information likelihood Le(u) to a memory 11b. A read-out controller 11c subjects the external-information likelihood Le(u) to interleaving and deinterleaving as appropriate by reading the external-information likelihood Le(u) out of the memory 11b, and outputs the result as a priori likelihood L(u′) used in the next cycle of MAP decoding.
In MAP decoding from the second cycle onward, turbo decoding is such that [signal ya+a priori likelihood L(u′)] is used as the input signal ya. Accordingly, in the second cycle of MAP decoding, the external-information likelihood calculation unit 8 outputs the external-information likelihood Le(u), which is used in the third cycle of MAP decoding, using the a posteriori likelihood L(u) output from the a posteriori probability calculation unit 7 and the decoder-input signal
[=signal ya+a priori likelihood L(u′)].
The write controller 11a writes the external-information likelihood Le(u) to the memory 11b. The read-out controller 11c subjects the external-information likelihood Le(u) to interleaving and deinterleaving as appropriate by reading the external-information likelihood Le(u) out of the memory 11b, and outputs the result as a priori likelihood L(u′) used in the third cycle of MAP decoding. Thereafter, and in similar fashion, the external-information likelihood calculation unit 8 outputs the external-information likelihood Le(u). The following equation is established using the log value of each value:L(u)=Lya+L(u′)+Le(u)  (2)and therefore the external-information likelihood calculation unit 8 is capable of obtaining the external-information likelihood Le(u) in accordance with the following equation:Le(u)=L(u)−Lya−L(u′)  (3)where L(u′)=0 holds the first time.
In a case where the decoded data u is output finally, the write controller 11a writes this decoded data to the memory 11b. In other cases, however, the write controller 11a writes the external-information likelihood Le(u) to the memory 11b. In a case where the decoded data u is output, the read-out controller 11c outputs the decoded data by reading it out of memory in the order in which it was written. In a case where the external-information likelihood Le(u) is read out, the read-out controller 11c performs read-out in accordance with a read-out sequence specified by the interleave controller 11d, thereby outputting (interleaving) data. A memory 11e, which has a RAM 11e1 and a RAM controller 11e2, stores the external-information likelihood Le(u) as a priori likelihood L(u′).
FIG. 35 is a diagram useful in describing the sequence of turbo decoding. As is obvious from FIG. 29, turbo decoding is repeated a plurality of times treating a first half of decoding which uses ya, yb and a second half of decoding which uses ya, yc as one set.
In the first half of decoding processing the first time, decoding is performed using receive signals ya, yb and the likelihood L(u1) obtained is output. Next, the a priori probability Le(u1) is obtained in accordance with Equation (3) [where L(u1′)=0 holds], this is interleaved and L(u2′) is obtained.
In the second half of decoding processing the first time, a signal obtained by interleaving the receive signal ya and the a priori likelihood L(u2′) obtained in the first half of decoding processing are regarded as being a new receive signal ya′, decoding is performed using ya′ and yc, and the likelihood (u2) obtained is output. Next, the a priori likelihood Le(u2) is found in accordance with Equation (3) and this is interleaved to obtain L(u3′).
In the first half of decoding processing the second time, the receive signal ya and the a priori likelihood L(u3′) obtained in the second half of decoding processing are regarded as being a new receive signal ya′, decoding is performed using ya′ and yb, and the likelihood (U3) obtained is output. Next, the a priori likelihood Le(u3) is found in accordance with the above equation, this is interleaved and L(u4′) is obtained.
In the second half of decoding processing the second time, a signal obtained by interleaving the receive signal ya and the a priori likelihood L(u4′) obtained in the first half of decoding processing are regarded as being a new receive signal ya′, decoding is performed using ya′ and yc, and the likelihood (u4) obtained is output. Next, the a priori likelihood Le(u4) is found in accordance with Equation (3) and this is interleaved to obtain L(u5′). The above-described decoding processing is subsequently repeated.
Second MAP Decoding Method According to the Prior Art
FIG. 36 is a block diagram of a turbo decoder that adopts a second MAP decoding method according to the prior art. This turbo decoder has a structure identical with that of the turbo decoder shown in FIG. 31. This differs in terms of calculation of backward probability β, the storage operation thereof and the overall timing of calculation of a posteriori probability.
FIG. 37 is a diagram useful in describing the operating principle of the MAP unit, and FIG. 38 is a time chart of the MAP unit. Here information length N is divided into blocks of length L each, and decoding is performed using L as the basic unit. For the sake of description, it will be assumed that the beginning of the information is 0, that the end thereof is N, and that the information in between is L1, L2, L3, . . . , Lx at intervals L.
{circle around (1)} Initially, the backward-probability calculation unit 5 calculates backward probabilities from k=N to k=0. At this time backward probabilities βk(m) of each state (m=0 to 7) in Lx, . . . , L3, L2 every L are written to a discrete-β memory 10a2 of the backward-probability RAM 10, and backward probabilities βk(m) of each state from k=L1 to k=0 are written continuously to a continuous-β memory 10a1.
{circle around (2)} Next, the forward-probability calculation 3 calculates forward probabilities from k=0 to k=L1. At the same time, the joint-probability calculation unit 6 reads backward probabilities from k=0 to k=L1 out of the continuous-β memory 10a1 and calculates joint probability based on both forward and backward probabilities. Calculation of a posteriori probability and calculation of external-information likelihood are thenceforth performed in order.
{circle around (3)} At the same time as the calculation performed at {circle around (2)}. above, the backward-probability calculation unit 5 reads the result of calculation of backward probability at k=L2 out of the discrete-β memory 10a2, calculates backward probabilities from k=L2 to k=L1 using the above result as the initial value, and stores the backward probabilities in the continuous-β memory 10a1. Since the calculations of {circle around (2)}. and {circle around (3)}. are executed by separate circuits, they can be performed simultaneously.
{circle around (4)} Next, the forward-probability calculation 3 calculates forward probabilities from k=L1 to k=L2. At the same time, the joint-probability calculation unit 6 reads backward probabilities from k=L1 to k=L2 out of the continuous-β memory 10a1 and calculates joint probability based on both forward and backward probabilities. Calculation of a posteriori probability and calculation of external-information likelihood are thenceforth performed in order.
{circle around (5)} At the same time as the calculation performed at {circle around (4)}. above, the backward-probability calculation unit 5 reads the result of calculation of backward probability at k=L3 out of the discrete-β memory 10a2, calculates backward probabilities from k=L3 to k=L2 using the above result as the initial value, and stores the backward probabilities in the continuous-β memory 10a1. Since the calculations of {circle around (4)}. and {circle around (5)}. are executed by separate circuits, they can be performed simultaneously.
Operations similar to the above are repeated and decoded results are output up to k=N.
Decoding time in this case is 2N in a single MAP decoding operation, as illustrated in FIG. 38. Performing this MAP decoding operation twice signifies a single iteration of turbo decoding. If the number of iterations of turbo decoding is eight, therefore, the decoding time is 32N for turbo decoding in its entirety.
Third MAP Decoding Method According to the Prior Art
FIG. 39 is a block diagram of a turbo decoder that adopts a third MAP decoding method according to the prior art. Components identical with those of the turbo decoder of FIG. 31 are designated by like reference characters. This arrangement differs in the provision of two backward-probability calculation units 5a, 5b for executing the backward probability calculations in parallel simultaneously, and in the timing of the overall operation of calculation of a posteriori probability. The third MAP decoding method is a method disclosed in Andrew J. Viterbi, “An Intuitive Justification and a Simplified Implementation of the MAP Decoder for Convolutional Codes”, IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATION, VOL. 16, NO. 2, FEBRUARY 1998.
This method is advantageous in that the size of the backward-probability RAM can be reduced and processing can be speeded up. Disadvantages are a slight deterioration in characteristics and the fact that two backward-probability calculation units are required. FIG. 40 is a diagram useful in describing the operating principle of the MAP unit, and FIG. 41 is a time chart of the MAP unit.
{circle around (1)} First, the first backward-probability calculation unit 5a performs the calculation of backward probability from k=2L to k=0. In this calculation of backward probability, the backward probability βk(m) is not calculated from k=N; calculation starts from an intermediate position k=2L. As a consequence, the backward probability βk(m) found over k=2L to k=L in the first half cannot be trusted and is discarded. The backward probability βk(m) found over k=L to k=1 in the second half can be trusted and therefore this is stored in the backward probability RAM 10.
{circle around (2)} Next, if the backward probability βk(m) at k=0 is found from k=L−1, the forward-probability calculation 3 performs the calculation of forward probability at k=0, the joint-probability calculation unit 6 performs the calculation of joint probability based upon the result of forward probability calculation and the result of backward probability calculation at
k=0, and the a posteriori probability calculation unit 7 and external-information likelihood calculation unit 8 perform the calculations of a posteriori probability and external information likelihood. Next, the calculation of forward probability at k=1 is performed, and the calculations of joint probability, a posteriori probability and external information likelihood are executed based upon the result of forward probability calculation and the result of backward probability calculation at k=1. Thereafter, and in similar fashion, calculation of forward probability at k=L−1 is performed, and the calculations of joint probability, a posteriori probability and external information likelihood are executed based upon the result of forward probability calculation and the result of backward probability calculation at k=L−1.
{circle around (3)} The second backward-probability calculation unit 5b starts calculation of backward probability from k=3L to k=L in sync with the start of calculation of backward probability at k=L1 by the first backward-probability calculation unit 5a. The backward probability βk(m) found over k=3L to k=2L in the first half cannot be trusted and therefore is discarded. The backward probability βk(m) found over k=2L to k=L in the second half can be trusted to a certain degree and therefore this is stored in the backward probability RAM 10.
{circle around (4)} If the backward probability βk(m) at k=L is found from k=2L−1, the forward-probability calculation 3 performs the calculation of forward probability at k=L, the joint-probability calculation unit 6 performs the calculation of joint probability based upon the result of forward probability calculation and the result of backward probability calculation at k=L, and the a posteriori probability calculation unit 7 and external-information likelihood calculation unit 8 perform the calculations of a posteriori probability and external information likelihood. Next, the calculation of forward probability at k=(L+1) is performed, and the calculations of joint probability, a posteriori probability and external information likelihood are executed based upon the result of forward probability calculation and the result of backward probability calculation at k=L+1. Thereafter, and in similar fashion, calculation of forward probability at k=2L−1 is performed, and the calculations of joint probability, a posteriori probability and external information likelihood are executed based upon the result of forward probability calculation and the result of backward probability calculation at k=2L−1.
{circle around (5)} The first backward-probability calculation unit 5a starts calculation of backward probability from k=4L to k=2L in sync with the start of calculation of backward probability at k=L2 by the second backward-probability calculation unit 5b. The backward probability βk(m) found over k=L3 to k=L2 in the second half is stored in the backward probability RAM 10.
Operations similar to the foregoing are repeated subsequently and decoded results are output up to k=N.
Decoding time in this case is 2L+N by a single element decoding, as illustrated in FIG. 40. If the number of iterations is made eight, then the length of time is 16×(2L+N) for turbo decoding in its entirety. Generally, L is made four to five times the constraint length K. Therefore, if, e.g., K=4 holds, then L is 16 to 20. Since 2L is sufficiently small in comparison with N, decoding time is approximately 16N.
The characterizing features of the examples of the prior art are summarized in Table 1 below.
TABLE 1ERROR RATESCALECHARACTER-OF HARDWARECOMPUTATIONISTICLOGICMEMORYSPEEDPRIOR⊚⊚XΔART 1PRIOR⊚⊚◯ΔART 2PRIOR◯◯⊚⊚ART 3⊚: Excellent, ◯: Good, Δ: Fair, X: Poor
With turbo decoding, the computations for such element decoding (MAP decoding) are repeated. It is known that increasing the number of iterations improves the error-rate characteristic. FIG. 42 illustrates an example of error characteristics that correspond to iteration counts (it) of 1, 2, 4, 8 and 16. FIG. 42 shows that as the number of iterations increases, gain saturates. Further, a proportionately longer decoding time is necessary if the number of iterations increases. In general, therefore, it is said that the appropriate number of iterations is on the order of eight, taking both of these factors into consideration. It should be noted here that a single iteration means one iteration involves performing element decoding twice. Eight iterations, therefore, means that the element decoding operation is performed 16 times.
Accordingly, the computation speed of this element decoding becomes the computation speed of turbo decoding per se. For example, according to the Ministry of Home Affairs, the maximum information rate in a fourth-generation (new generation) mobile communications system is greater than 100 Mbps. If real-time processing cannot be executed in this case, it is necessary to provide a commensurate number of turbo decoders in parallel.
For example, if the number of bits of the unit of turbo decoding (information bits+tail bits) is N and the number of iterations is eight with the first MAP decoding method of the prior art, then N×2 is the number of clocks required to perform MAP decoding one time. The number of clocks required for turbo decoding, therefore, is N×2×2×8. There are several tail bits, however. In order to simplify the description, therefore, the number of these tail bits is ignored. In view of the foregoing, the number of clocks required for turbo decoding is about 32N. In other words, there is a delay that is 32 times the signal length N, and 32 turbo decoders are necessary even if a clock of 100 MHz is used. More specifically, if it is assumed that one frame is equal to 100 μs, then the information per frame will be 10,000 bits at 100 Mbps. In order to decode 10,000 bits of information by performing turbo decoding with eight iterations using a 100-MHz clock, we have(10,000)×2×2×8/100 MHz=3.2 msIt is assumed here that one frame is equal to 100 μs. However, since the amount of data processed per unit time is the same even if the size of one frame is changed, the necessary number of turbo decoders is 32.
A block diagram of the turbo decoder in this case is as shown in FIG. 43 and the associated time chart is as illustrated in FIG. 44. Components in FIG. 43 identical with those shown in FIG. 31 are designated by like reference characters. Turbo decoders 1 to 32 are identical in structure.
The foregoing is the case for the first MAP decoding method according to the prior art but what holds for the first MAP decoding method holds similarly for the second and third MAP decoding methods. In the case of the third MAP decoding method, however, the fact that the inherent computation speed is high means that turbo decoding time is about 16N under similar conditions. The number of turbo decoders necessary, therefore, is 16.
Thus, with the turbo decoding method of the prior art, a plurality of turbo decoders become necessary when the information rate is high. Moreover, even if a plurality of turbo decoders are provided, the time necessary for turbo decoding cannot be shortened sufficiently (it is 3.2 ms in the above-described example), and an increase in delay time becomes a problem.